1. Technical Field
This invention generally relates to computer systems. More specifically, this invention relates to a method and apparatus for collecting profile data for a computer program.
2. Background Art
The development of the EDVAC computer system in 1948 is generally considered the beginning of the computer era. Since that time, dramatic advances in both hardware and software (e.g., computer programs) have drastically improved the performance of computer systems. Modern software has become very complex when compared to early computer programs. Many modern computer programs have tens or hundreds of thousands of instructions. The execution time (and hence, performance) of a computer program is very closely related to the number of instructions that are executed as the computer program runs. Thus, as the size and complexity of computer programs increase, the execution time of the computer program increases as well.
Unlike early computer programs, modern computer programs are typically written in a high-level language that is easy to understand by a human programmer. Special software tools known as compilers and linkers take the human-readable form of a computer program, known as "source code", and convert it into "machine code" or "object code" instructions that may be executed by a computer system. Because a compiler and its associated linker generate the stream of machine code instructions that are eventually executed on a computer system, the manner in which the compiler and linker package procedures within a module affects the performance of the computer program.
In particular, the ordering of procedures within a module affects the performance of the memory paging system in a computer system. Nearly all computer systems have an auxiliary storage, such as a hard disk drive, that has large storage capacity, and is relatively inexpensive yet slow compared to main memory. Main memory is typically comprised of Random Access Memory (RAM), which has a much smaller storage capacity and is more expensive than primary storage, yet it is very fast. Instructions and data are typically moved between primary storage and main memory in "pages." A "page" consists of a predefined number of bytes (typically a power of two), and is the fundamental unit of transfer between primary storage and main memory. A predetermined number of pages are typically set aside in main memory for storing pages as they are moved between auxiliary storage and main memory. When a processor within a computer system begins executing a computer program, the memory paging system fills the portion of main memory allocated to paging with pages from primary storage. When the processor needs data that is not in any of the pages in main memory, the memory paging system selects one or more pages that are replaced by new pages from primary storage. Swapping pages in and out of memory requires time and system resources, and therefore degrades system performance. In other words, the fewer the number of page swaps, the better.
Many modern software development environments include a profiling mechanism that uses information collected about a program's run-time behavior (known as profile data) to improve optimization of that program. "Profile data" as used herein means any estimates of execution frequencies in a computer program. Using profile data, a compiler, a linker, or a separate optimizer program may make decisions during the compilation and/or linking of a computer program regarding the preferred order of procedures within the computer program in order to optimize the performance of the computer system.
Profile data may be generated in a number of different ways. One way of generating profile data is to perform a static analysis of the program code to estimate the execution frequencies of procedures in the computer program. Other methods are known that dynamically collect information about a computer program as it runs.
One type of dynamic profiler is known as an instrumenting profiler. An instrumenting profiler inserts special instrumentation code known as "hooks" at important points in the computer program (such as procedure calls). An instrumenting profiler generally defines a counter for each program event of interest, and the instrumentation hooks increment their corresponding counters. As the instrumented program executes, these hooks cause data counters to be incremented, recording the profile history directly. When the sample run of the computer program is complete, the counters contain profile data. In the case of procedure reordering, the profile data of interest is the number of times each procedure is called by other procedures in the computer program.
Procedures may generally be called in two different ways. Direct procedure calls invoke a procedure using its name. Indirect procedure calls invoke a procedure using a variable, index, procedure pointer, or other indirect method that makes it impossible for a profiler to tell which procedure will be called when it is inserting instrumentation hooks into the computer program. Instrumenting direct procedure calls is straightforward. A counter is allocated for each direct procedure call within a selected procedure, and the instrumentation hook at a direct call site within the selected procedure simply increments the counter corresponding to the procedure called. Instrumenting indirect procedure calls, however, is a complex problem that known prior art solutions do not adequately address. Most prior art profilers simply ignore indirect call sites, thereby losing important profile data. Without improved apparatus and methods for collecting profile data at indirect call sites, the profile data will lack important information relating to indirect procedure calls, and the computer industry will never fully realize the benefits of profiling.